from typing import List

"""
14. 最长公共前缀
https://leetcode.cn/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150
"""


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = []
        for t in zip(*strs):
            if len(set(t)) == 1:
                res.append(t[0])
            else:
                break
        return ''.join(res)
    def longestCommonPrefix2(self, strs: List[str]) -> str:
        if not strs:
            return ""

        for i in range(len(strs[0])):
            for s in strs:
                if i == len(s) or s[i] != strs[0][i]:
                    return strs[0][:i]

        return strs[0]


if __name__ == "__main__":
    print(Solution().longestCommonPrefix(["flower","flow","flight"]))
    # print(Solution().longestCommonPrefix(["dog", "racecar", "car","a"]))
    print(Solution().longestCommonPrefix(["ab","a"]))
    print(Solution().longestCommonPrefix(["a"]))
